#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "trie.h"

void node_init(Trie_node *tr)
{
	int i;
	for (i = 0; i < MAX_INDEX_LEN; i ++) {
		tr->branch[i] = NULL;
		tr->ifend = 0;
	}
}

void queue_init()
{	
	trie_queue = (Trie_queue *)malloc(sizeof(Trie_queue));
	trie_queue->node_size = NODE_SIZE;
	trie_queue->node_total = trie_queue->node_size * sizeof(Trie_node);
	trie_queue->node_cursor = 0;
	trie_queue->trie_root = (Trie_node *)malloc(trie_queue->node_total);
	
	int i = 0;
	for (i=0;i<trie_queue->node_size;i++) {
		node_init(&trie_queue->trie_root[i]);
	}
}

int queue_realloc()
{
	Trie_node *temp;
	
	trie_queue->node_size += NODE_SIZE;
	trie_queue->node_total += NODE_SIZE * sizeof(Trie_node);
	temp = (Trie_node *)realloc(trie_queue->trie_root, trie_queue->node_total);
	if(!temp) {	
		return 0;
	}
	trie_queue->trie_root = temp;
	int i = 0;
	i =	trie_queue->node_cursor + 1;
	for (;i<trie_queue->node_size;i++) {
		node_init(&trie_queue->trie_root[i]);
	}
	return 1;
}

int words_add(char *word)
{
	int char_code;
	int state = -1;
	
	Trie_node *location;
	location = trie_queue->trie_root;
	
	while (*word) {
        char_code = tolower(*word) & 0xFF; //取得当前字节的ASCII码
		if (location->branch[char_code] == NULL) {
			if (trie_queue->node_cursor == trie_queue->node_size - 1) {
				//realloc queue
				queue_realloc();
			}
			//printf("char_code: %d\n", char_code);
			location->branch[char_code] = &trie_queue->trie_root[trie_queue->node_cursor];
			if (location->branch[char_code]) {
				state = 1;
			} else {
				return state;
			}
			trie_queue->node_cursor++;
		}
		location = location->branch[char_code];
		if (location->ifend  != 1) {
			location->ifend  = 2;
			state = 1;
		} else {
			state = 0;
		}
		word ++;
	}
	location->ifend  = 1;
	return state;
}

int words_delete(char *word) 
{
	int state = -1;
	int char_code = -1;
	
	Trie_node *location;
	location = trie_queue->trie_root;
	
	while(*word) {
        char_code = tolower(*word) & 0xFF;
         
		if(!location->branch[char_code]) {
			break;
		}
		location = location->branch[char_code];
		
		word ++;
	}

	if (location->ifend == 1) {
		location->ifend = 2;
		state = 1;
	} else {
		state = 0;
	}
	return state;
}

int words_filter(char *words, char *info) 
{
	int pos = 0, next_pos = 0, jump = 0, result = 0;
	int start = 0, end = -1;
	int wordslen = 0;
	Trie_node *temp = NULL;
	Trie_node *root = NULL;
	root = trie_queue->trie_root;
	
	wordslen = strlen(words);
	for (;pos < wordslen;) {
		jump = jump_byte_utf8(words, pos);
		if (next_pos == 0) {
			next_pos = pos + jump;
		}
		if (temp) {
			temp = words_search(words, pos, pos+jump, temp);
		} else {
			temp = words_search(words, pos, pos+jump, root);
		}

		if (temp) {
			result = temp->ifend;
		} else {
			result = 0;
			temp = NULL;
		}
		if (result == 1) {
			end = pos+jump-1;
			break;
		} else if (result == 2) {
			pos += jump;
		} else {
			pos = start = next_pos;
			next_pos = 0;
		}
	}
	
	if (start == -1 || end == -1) {
		sprintf(info, "%d|%d", -1, -1);
	} else {
		sprintf(info, "%d|%d", start, end-start+1);
	}
	return 1;
}

Trie_node *words_search(char *words, int start, int end, Trie_node *tr) 
{
	int wordAscii = 0, i = 0;
	Trie_node *location;
	location = tr;
	for(i=start;i<end;i++) {
        wordAscii = tolower(words[i]) & 0xFF;
		if (!location->branch[wordAscii]) return NULL;
		location = location->branch[wordAscii];
	}
	return location;
}

int jump_byte_utf8(char *words, int pos) 
{
	if ((words[pos] & 0xFF) >=  0xC0 
			&& (words[pos] & 0xFF) < 0xE0 
			&& words[pos + 1] ) {
				return 2;
	} else if ((words[pos] & 0xFF) >=  0xC0 
			&& (words[pos] & 0xFF) <  0xF0 
			&& words[pos + 1] && words[pos + 2]) {
				return 3;
	} else if ((words[pos] & 0xFF) >=  0xC0 
			&& (words[pos] & 0xFF) <  0xF8 
			&& words[pos + 1] 
			&& words[pos + 2] 
			&& words[pos + 3]) {
				return 4;				
	}
	return 1;
}

int check(char *words, Trie_node *root, char *info) 
{
	int pos = 0, next_pos = 0, jump = 0, result = 0;
	int start = 0, end = 0;
	int wordslen = 0;
	Trie_node *temp = NULL;
	
	wordslen = strlen(words);
	for (;pos < wordslen;) {
		jump = jump_byte_utf8(words, pos);
		if (next_pos == 0) {
			next_pos = pos + jump;
		}
		if(temp) {
			temp = word_search(words, pos, pos+jump, temp);
		} else {
			temp = word_search(words, pos, pos+jump, root);
		}

		if(temp) {
			result = temp->ifend;
		} else {
			result = 0;
			temp = NULL;
		}
		if (result == 1) {
			end = pos+jump-1;
			break;
		} else if (result == 2) {
			pos += jump;
		} else {
			pos = start = next_pos;
			next_pos = 0;
		}
	}
	sprintf(info, "%d|%d", start, end);
	return 1;
}

Trie_node *word_search(char *words, int start, int end, Trie_node *tr) 
{
	int wordAscii = 0, i = 0;
	Trie_node *location;
	location = tr;
	for(i=start;i<end;i++) {
        wordAscii = tolower(words[i]) & 0xFF;
		if (!location->branch[wordAscii]) return NULL;
		location = location->branch[wordAscii];
	}
	return location;
}